/*
 * @Author: YiY
 * @Date: 2024-01-08 09:04:11
 * @LastEditTime: 2024-01-09 11:24:51
 */

function mergeSort(list) {
  let len = list.length

  if (len < 2) return list // 1,0

  if (len >= 2) {
    let lList = [], rList = [], result = []
    let mid = Math.floor(len / 2)
    //len为3时，子数组lent为1，mid为1，lList为list[0],slice仅包含begin
    lList = mergeSort(list.slice(0, mid))
    rList = mergeSort(list.slice(mid))

    let l = 0, r = 0
    while (l + r != len) {
      if (l == lList.length) { result.push(rList[r++]); continue }
      if (r == rList.length) { result.push(lList[l++]); continue }
      lList[l] < rList[r] ? result.push(lList[l++]) : result.push(rList[r++])
    }
    return result
  }
}

// 测试数据
let arr = [9, 8, 7, 6, 5, 4, 3, 2, 1];
console.log("原始数组：", arr);
console.log("归并排序后：", mergeSort(arr));
